# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/4/19

"""
报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。

给定一个正整数 n ，输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

输入: 1
输出: "1"
示例 2:

输入: 4
输出: "1211"

"""


class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        temp = "1"
        for i in range(1, n):
            temp = self.get_next(temp)
        return temp

    def get_next(self, now):
        """
        :param now: 当前的字符串
        :return: str  下一个字符串
        """
        result = ""
        stack = []
        length = len(now)
        for i in range(0, length):
            is_emp = False
            if len(stack) == 0:
                is_emp = True
                stack.append(now[i])
            if i == length - 1:
                if is_emp:
                    result += "1" + stack[0]
                    break
                else:
                    top = stack[len(stack) - 1]
                    if top != now[i]:
                        result += str(len(stack)) + str(top) + "1" + now[i]
                    else:
                        result += str(len(stack) + 1) + stack[0]
                break
            else:
                top = stack[len(stack) - 1]
                if top != now[i]:
                    result += str(len(stack)) + str(top)
                    stack.clear()
                    stack.append(now[i])
                if top == now[i] and not is_emp:
                    stack.append(now[i])
        return result


if __name__ == "__main__":
    s = Solution()
    get_next = s.get_next("111221")
    print(get_next)
